# LeetCode 315. 计算右侧小于当前元素的个数
# https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/
from typing import List


class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        def mergeSort(left, right):
            if left >= right:
                return 0

            mid = (left + right) // 2
            mergeSort(left, mid)
            mergeSort(mid + 1, right)
            tmp = []
            i, j = left, mid + 1
            while i < mid + 1 or j < right + 1:
                if i == mid + 1:
                    tmp.append(nums[j])
                    j += 1
                elif j == right + 1:
                    tmp.append(nums[i])
                    if nums[i][1]!=nums[right][1]:
                        result[nums[i][0]] += (j - mid - 1)
                    i += 1

                elif nums[i][1] <= nums[j][1]:
                    tmp.append(nums[i])
                    result[nums[i][0]] +=  (j - mid - 1)
                    i += 1

                else:
                    tmp.append(nums[j])
                    j += 1

                    # 会超时
                    # for k in range(i, mid + 1):
                    #     result[nums[k][0]] += (j - mid - 1)


            nums[left:right + 1] = tmp
            # print(result)


        n = len(nums)
        result = [0] * n
        nums = list(enumerate(nums))
        mergeSort(0, n - 1)
        return result


# 二分
# class Solution:
#     def countSmaller(self, nums: List[int]) -> List[int]:
#         nums_sort = SortedList()
#         result = []
#         for index, num in enumerate(reversed(nums)):
#             index = nums_sort.bisect_left(num)
#             result.append(index)
#             nums_sort.add(num)
#         return result[::-1]


class BIT:
    def __init__(self, n):
        self.tree = [0] * (n + 1)

    def lowbit(self, x):
        return x & (-x)

    def update(self, i, delta):
        i += 1
        while i < len(self.tree):
            self.tree[i] += delta
            i += self.lowbit(i)

    def prefix_sum(self, i):
        i += 1
        summ = 0
        while i > 0:
            summ += self.tree[i]
            i -= self.lowbit(i)
        return summ


class Solution2:
    def countSmaller(self, nums: List[int]) -> List[int]:
        n = len(nums)

        uniques = sorted(set(nums))
        rank_map = {v: i for i, v in enumerate(uniques)}

        tree = BIT(len(uniques))

        result = [0] * n
        for i in range(n - 1, -1, -1):
            rank = rank_map[nums[i]]
            tree.update(rank, 1)
            result[i] = tree.prefix_sum(rank - 1)
        return result


if __name__ == '__main__':
    nums = [5, 2, 6, 2]
    # nums = [-1]
    # nums = [-1, -1]
    # nums = [0, 2, 1]
    # nums = [26, 78, 27, 100, 33, 67, 90, 23, 66, 5, 38, 7, 35, 23, 52, 22, 83, 51, 98, 69, 81, 32, 78, 28, 94, 13, 2, 97, 3,
    #  76, 99, 51, 9, 21, 84, 66, 65, 36, 100, 41]
    result = Solution().countSmaller(nums)
    print(result)
    result2 = Solution2().countSmaller(nums)
    print(result2)
